/*
 * Alvin Baldemeca
 * HW4, TCSS 343
 * UWT May 17,2014
 * Prof. Ling Ding
 * 
 * 
 */

package HW4;
import java.math.*;
import java.util.HashMap;

import static java.lang.System.out;
public class Homework4 {
	
	
	/**
	 * This method implements Horspool's algorithm from matching the string pattern.
	 * @param text - the string to match the pattern to
	 * @param pattern - the pattern to match to the string 
	 * @return - the boolean_int class that contains a boolean value if the pattern 
	 *         matches the text and the number of comparison made. 
	 */
	public static boolean_int Horspool(String text, String pattern)
	{
		//add your code here using Horspool algorithm for String Matching
		boolean_int ret = new boolean_int();
		int plen = pattern.length() -1 ;
		HashMap<Character, Integer> table = new HashMap<Character, Integer>();
		for(int i = 0; i < pattern.length() - 2; i++)
		{
			table.put(pattern.charAt(i), plen-i );
	    }
		
		int j = plen;
		while( j <= text.length()-1)
		{
			ret.count++;
			int k = 0;
			while(k<=plen && text.charAt(j-k) == pattern.charAt(plen - k))
			{
			  ret.count++;
	          k++;
			}
			
			   if( k == pattern.length())
		       {
					   ret.bool_tag = true;
		               return ret;//j - pattern.length() +1;
		       }else{
		    	   
		        	  if(table.get(text.charAt(j - k)) == null)
		        	  {
		        		  j = j + pattern.length();
		        	  }else{
		        		  
		        	  
		        	  	j = j + table.get(text.charAt(j - k));
		        	  }
		          } 
			
		}
		
		
		return ret;
	}
	
	/**
	 * This method implements a brute force (BF) algorithm from matching the string pattern.
	 * @param text - the string to match the pattern to
	 * @param pattern - the pattern to match to the string 
	 * @return - the boolean_int class that contains a boolean value if the pattern 
	 *         matches the text and the number of comparison made. 
	 */
	public static boolean_int bruteforceforStringMatching(String text, String pattern)
	{
		//add your code here using bruteforce algorithm for String Matching
		
		boolean_int ret = new boolean_int();
		
		for(int i = 0; i < text.length() - pattern.length() + 1 ; i++)
		{
			
			for(int j = 0; j < pattern.length(); j++)
			{
				ret.count++;
				if(text.charAt(j + i) != pattern.charAt(j))
				{
					
					break;
				}	

			 if(j == pattern.length() -1)
			 {
				 ret.bool_tag = true;
				 return ret;
			 }
			}
			
		}
		return ret;
	}

	/**
	 * This method returns the integer value for the maximum absolute difference 
	 * between an integer in A[] and B[]
	 * @param A - the first unsorted integer array
	 * @param B - the second unsorted integer array
	 * @return - the integer value for the maximum abslute difference
	 */
	public static int getMaxDiff(int[] A, int[] B)
	{
		heapSort(A);
		heapSort(B);
		int a = Math.abs(A[0] - B[B.length -1]);
		int b = Math.abs(A[A.length - 1] - B[0]);
		return (a > b) ? a : b ;
	}

	/**
	 * This implements a heapSort on the integer array provided.
	 * @param A - the integer array to sort
	 */
	public static void heapSort(int[]A)
	{
		int temp;
		build_max_heap(A);
		for(int i = A.length - 1; i > 1; i--)
		{
			temp = A[0];
			A[0] = A[i];
			A[i] = temp;
			max_heapify(A, 0, i);
		}
		
	}
	
	/**
	 * This creates a max heap given an integer array.
	 * @param A - the integer array to build into a max heap
	 */
	public static void build_max_heap(int[]A)
	{
		
		for(int i = A.length / 2; i >= 0; i--)
		{
			max_heapify(A, i, A.length);	
		}

	}
	
	/**
	 * This ensures a max heap at the node index pointed at i for the 
	 * arrlen provided. 
	 * @param A - the array to max heapify
	 * @param i - the index in the array to heapify
	 * @param arrlen - max heapify up to this index
	 */
	public static void max_heapify(int A[], int i, int arrlen)
	{
	
		int temp = A[i];
		int lchild = i*2 + 1;
		int rchild = lchild + 1;
		
		if(lchild < arrlen && A[i] > A[lchild] && rchild < arrlen && A[i] > A[rchild])
		{
			return;
		}else if(lchild < arrlen && rchild < arrlen )
		{
			if(A[lchild] > A[rchild])
			{
				A[i] = A[lchild];
				A[lchild]= temp;
				max_heapify(A, lchild, arrlen);
			}else
			{
				
				A[i] = A[rchild];
				A[rchild]= temp;
				max_heapify(A, rchild, arrlen);
			}
		}
		else if(i*2 < arrlen - 1)
		{
			A[i] = A[lchild];
			A[lchild]= temp;
			max_heapify(A, lchild, arrlen);
		}
	
	}
	
	
	/**
	 * This method returns one of the longest increasing subsequence in
	 * the array that's provided.
	 * @param a - the array to get the longest increasing subsequence
	 * @return - the array containing the longest increasing subsequence
	 */
	public static int[] lisubsq(int[] a)
	{
		int index = 0;
		int[] reference = new int[a.length];
		int[] parent = new int[a.length];
		reference[0] = 0;
		parent[0] = 0;
	    
		if(a.length <= 1)
		{
			return a;
		}
	
		for(int i = 1; i < a.length; i++)
		{
			if(a[i] > a[reference[index]])
			{
				reference[++index] = i;
				parent[i] = i;
			}else
			{
				for(int j = 0; j <= index; j++)
				{
					if(a[i] < a[reference[j]] )
					{
						parent[i] = reference[j];
						reference[j] = i;				
						break;
					}
				}
			}
		}
		
		int ret[] = new int[index+1];
		ret[index] = a[reference[index]];
		for(int i = index - 1; i >= 0; i--)
		{
			while(reference[i] > reference[i+1])
			{
				reference[i] = parent[reference[i]];
			}
			ret[i] = a[reference[i]];
		}
			
		return ret;
	}
	
	/**
	 * The main file where methods are tested
	 * @param args - command line arguments which are not used.
	 */
	public static void main(String[] args)
	{
		int A[] = {100, 3, 12, 63, -400, -900, 47, 12, 22, 14, 13, 66, 0, -12 };
		int B[] = {3, 4, 27, 31, 39, 43, 55, 70, 74, 81, 85, 93, 98};
		//int seq[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
		int seq[] = {7,13,45,67,12,3,2,1,99,76};
		int lis[] = lisubsq(seq);
		//int B [] = {3, 85, 93, 74, 81, 43, 55, 70, 31, 4, 39, 27, 98};
		//int B [] = {27, 85, 55, 74, 81, 43, 3, 70, 31, 4, 39, 93, 98};	
		//max_heapify(B, 0);
		int a = getMaxDiff(A, B);
		String t1 = "AAAZAAAZAAAZAAA";
		String p1 = "AAAA";
		String testtext =    "This is just a test to find a word.";
		String testpattern = "just a test";
		boolean_int retpat = Horspool(testtext, testpattern);
		out.println("Horspool text : This is just a test to find a word.\n"
				+ "Horspool pattern : just a test\n"
				+ "Hospool count is :" + retpat.count + " and the patter found is " 
				+ retpat.bool_tag + "\n");
		
		boolean_int bretpat = bruteforceforStringMatching(testtext, testpattern);
		out.println("BF text : This is just a test to find a word.\n"
				+ "BF pattern : just a test\n"
				+ "BF count is :" + bretpat.count + " and the patter found is " 
				+ bretpat.bool_tag + "\n");
		//build_max_heap(B);
		//heapSort(B);
		//boolean_int retpat = Horspool(t1, p1);
		//boolean_int retpat = bruteforceforStringMatching(t1, p1);
		//boolean_int retpat = bruteforceforStringMatching(testtext, testpattern);
		out.print("A : ");
		for(int i : A )
		{
			out.print(i + " ");
		}
		out.println();
		out.print("B : ");
		for(int i : B )
		{
			out.print(i + " ");
		}
		
		
		
		out.println("max|a-b| is : " + a);
		
	
		out.println("\nLIS for 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15");
		for(int i : lis )
		{
			out.print(i + " ");
		}
		out.println();
	}

}
